class Solution
{
public:
    int specialPerm(vector<int> &nums)
    {
        int n = nums.size();
        int subSetCount = 1 << n;

        // dp[c][i][mask] 表示已经选择了c+1个元素, 最后一个元素为nums[i]且已经选择的子集为mask的排列个数
        vector<vector<unordered_map<int, int>>> dp(n, vector<unordered_map<int, int>>(n));
        for (int i = 0; i < n; ++i)
        {
            dp[0][i][1 << i] = 1;
        }

        for (int selectedCount = 1; selectedCount < n; ++selectedCount)
        {
            for (int lastI = 0; lastI < n; ++lastI)
            {
                for (auto &[subSet, count] : dp[selectedCount - 1][lastI])
                {
                    for (int thisI = 0; thisI < n; ++thisI)
                    {
                        if ((1 << thisI) & subSet)
                        {
                            continue;
                        }
                        if (!(nums[lastI] % nums[thisI] == 0 || nums[thisI] % nums[lastI] == 0))
                        {
                            continue;
                        }
                        dp[selectedCount][thisI][(1 << thisI) | subSet] += count;
                        dp[selectedCount][thisI][(1 << thisI) | subSet] %= 1'0000'0000'7;
                    }
                }
            }
        }

        int result = 0;
        for (int i = 0; i < n; ++i)
        {
            result += dp[n - 1][i][subSetCount - 1];
            result %= 1'0000'0000'7;
        }
        return result;
    }

    // 将元素看作图, 余数为0的两个元素之间存在一条边, 遍历所有长度为n的路径
    // 最坏情况下复杂度O(n!), 会超时
    int specialPerm(vector<int> &nums)
    {
        unordered_map<int, vector<int>> adjTable;
        for (int num : nums)
        {
            for (int adjNum : nums)
            {
                if (num != adjNum && (num % adjNum == 0 || adjNum % num == 0))
                {
                    adjTable[num].push_back(adjNum);
                }
            }
        }
        auto dfs = [&](int start)
        {
            stack<pair<int, int>> s;
            int result = 0;
            unordered_set<int> visited;
            visited.insert(start);
            s.push({start, 0});
            while (!s.empty())
            {
                auto [node, next] = s.top();

                if (next == adjTable[node].size())
                {
                    s.pop();
                    if (!s.empty())
                    {
                        s.top().second++;
                    }

                    visited.erase(node);
                    continue;
                }
                int nextNode = adjTable[node][next];
                if (!visited.count(nextNode))
                {
                    s.push({nextNode, 0});
                    visited.insert(nextNode);
                    if (s.size() == nums.size())
                    {
                        ++result;
                        result %= 1'0000'0000'7;
                    }
                }
                else
                {
                    s.top().second++;
                }
            }
            return result;
        };

        int count = 0;
        for (int num : nums)
        {
            count += dfs(num);
            count %= 1'0000'0000'7;
        }
        return count;
    }
};